package Leetcode.Dichotomy;

import java.util.Arrays;
/**
 * @Author: kirito
 * @Date: 2024/4/3 15:00
 * @Description:
 * 统计公平数对的数目
 * 给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。
 *
 * 如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：
 *
 * 0 <= i < j < n，且
 * lower <= nums[i] + nums[j] <= upper
 *
 *
 * 示例 1：
 *
 * 输入：nums = [0,1,7,4,4,5], lower = 3, upper = 6
 * 输出：6
 * 解释：共计 6 个公平数对：(0,3)、(0,4)、(0,5)、(1,3)、(1,4) 和 (1,5) 。
 * 示例 2：
 *
 * 输入：nums = [1,7,9,2,5], lower = 11, upper = 11
 * 输出：1
 * 解释：只有单个公平数对：(2,9) 。
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 105
 * nums.length == n
 * -109 <= nums[i] <= 109
 * -109 <= lower <= upper <= 109
 */

public class countFairPairs {
    public static void main(String[] args) {
        int[] nums = {0, 1, 7, 4, 4, 5};

        System.out.println(countFairPairs(nums,3,6));
    }

    /**
     * 0 1 4 4 5 7
     * 要去重的话我得找到最右边的值呢，所以不能用闭区间？
     * @param nums
     * @param lower
     * @param upper
     * @return
     */
    public static long countFairPairs(int[] nums, int lower, int upper) {
        long ans = 0;
        Arrays.sort(nums);
        for (int j = 0; j < nums.length; ++j) {
            int r = lowerBound(nums, j, upper - nums[j] + 1);
            int l = lowerBound(nums, j, lower - nums[j]);
            ans += r - l;
        }
        return ans;
    }

    // 见 https://www.bilibili.com/video/BV1AP41137w7/
    private static int lowerBound(int[] nums, int right, int target) {
        int left = -1; // 开区间 (left, right)
        while (left + 1 < right) { // 区间不为空
            // 循环不变量：
            // nums[left] < target
            // nums[right] >= target
            int mid = (left + right) >>> 1;
            if (nums[mid] < target)
                left = mid; // 范围缩小到 (mid, right)
            else
                right = mid; // 范围缩小到 (left, mid)
        }
        return right;
    }
}
